#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 10, M = 2e6 + 10, MOD = 100003;
int n, m;
vector<int> edges[N];
int f[N];
int dist[N];
bool st[N];
void bfs()
{
    queue<int> q;
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    q.push(1);
    f[1] = 1;
    while (q.size())
    {
        int a = q.front();
        q.pop();
        for (auto& e : edges[a])
        {
            if (dist[a] + 1 < dist[e])
            {
                dist[e] = dist[a] + 1;
                f[e] = f[a];
                q.push(e);
            }
            else if (dist[a] + 1 == dist[e])
            {
                f[e] = (f[e] + f[a]) % MOD;
            }
        }
    }
}
void kck()
{
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<pii, vector<pii>, greater<pii>> q;
    dist[1] = 0;
    f[1] = 1;
    q.push({ 0,1 });
    while (q.size())
    {
        auto e = q.top();
        q.pop();
        int a = e.second;
        if (st[a])
            continue;
        st[a] = true;
        for (auto& s : edges[a])
        {
            if (dist[a] + 1 < dist[s])
            {
                dist[s] = dist[a] + 1;
                f[s] = f[a];
                q.push({ dist[s],s });
            }
            else if (dist[a] + 1 == dist[s])
            {
                f[s] = (f[s] + f[a]) % MOD;
            }
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    //bfs();
    kck();
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", f[i]);
    }
    return 0;
}